import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] arr=new int[]{-1,-1};
        if(nums.length==0){
            return arr;
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                if(map.containsKey(target)){
                    int val=map.get(target);
                    val=val+1;
                    map.put(nums[i],val);
                }else{
                    map.put(nums[i],i);
                }
            } else{
                map.put(nums[i],i);
            }
        }
        int end=0;
        for(int j=0;j<nums.length;j++){
            if(nums[j]==target){
                end=map.get(target);
                arr[0]=j;
                arr[1]=end;

            }
        }
        return arr;
    }
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> list = new ArrayList<>();
        int left = 1;
        int sum = 0;
        int right=1;
            while (right <= target / 2 + 1 && left <= right) {
                if (sum == target) {
                    int[] arr = new int[right - left+1];
                    for (int j = left; j <= right; j++) {
                        arr[j - left] = j;
                    }
                    list.add(arr);
                    sum = sum + right;
                }
                if (sum > target) {
                    sum = sum - left;
                    left++;
                }
                if (sum < target) {
                    sum = sum + right;
                    right++;
                }
            }
        return new int[list.size()][];
    }
    public int[] twoSum(int[] nums, int target) {
        int [] arr=new int[2];
        int left=0;
        int right=nums.length-1;
        for(int i=0;i<nums.length;i++){
            left=i;
            int sum=target-nums[left];
            while(left<=right){
                int mid=(left+right)/2;
                if(sum>nums[mid]){
                    left=mid+1;
                }else if(sum<nums[mid]){
                    right=mid-1;
                }else{
                    arr[0]=nums[left];
                    arr[1]=nums[mid];
                    return arr;
                }
            }
        }
        return arr;
    }

        public int[] twoSum1(int[] nums, int target) {
            if(nums.length==0){
                return new int[2];
            }
            int [] arr=new int[2];
            HashMap<Integer,Integer> map=new HashMap<>();
            for(int i=0;i<nums.length;i++){
                int val=target-nums[i];
                if(map.containsKey(val)){
                    arr[0]=target;
                    arr[1]=nums[i];
                }else{
                    map.put(nums[i],1);
                }
            }
            return arr;
        }

    public int strStr(String haystack, String needle) {
        char [] arr=haystack.toCharArray();
        char [] tmp=needle.toCharArray();
        int left=0;
        int aleft=0;
        while(left < arr.length&&aleft<tmp.length){
            if(arr[left]==tmp[aleft]){
                left++;
                aleft++;
            }
            else {
                int b=aleft;
                if (aleft!=0) {
                    aleft = 0;
                }
                 left=left-b+1;
                }
        }
        if(aleft==tmp.length){
            return left-aleft;
        }
        return -1;
    }
    public int[] singleNumbers(int[] nums) {
        int [] tmp=new int[2];
        int count=0;
        int len=nums.length;
        for(int i=0;i<len;i++){
            int j=0;
            for(;j<len;j++){
                if(nums[i]==nums[j]){
                    break;
                }
            }
            if(j==len){
                tmp[count]=nums[i];
                count++;
            }
        }
       return tmp;
    }
}